package leetcode_core.leetcode_4;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年10月25日 20:30
 */
public class shortestBridge {
    private int[][] steps = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    private Queue<int[]> queue = new LinkedList<>();
    private void dfs(int[][] grid,int x,int y,int n,int m){
        //x是行,y是列
        for(int i = 0;i<4;i++){
            int tx = x+steps[i][0];
            int ty = y+steps[i][1];
            if(tx<0 || ty<0 || tx>=n || ty>=m){
                continue;
            }
            if(grid[tx][ty] == 1){
                grid[tx][ty] = 2;
                dfs(grid,tx,ty,n,m);
            }
            if(grid[tx][ty] == 0){
                queue.offer(new int[]{tx,ty});//获取边缘点
            }
        }
    }
    public int shortestBridge(int[][] grid) {
        int n = grid.length;int m = grid[0].length;
        int startX=0,startY=0;
        int flag = 0;
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(grid[i][j] == 1){
                    startX = i;startY = j;
                    grid[i][j] = 2;
                    flag = 1;
                    break;
                }
            }
            if(flag == 1){
                break;
            }
        }
        //先对一座岛屿进行染色
        dfs(grid,startX,startY,n,m);
        //然后从队列中取数
        int ans = 0;
        while (!queue.isEmpty()){
            //扩展层数,这一层开始就要开始搭桥
            ans++;
            int size = queue.size();
            for(int k = 0;k<size;k++){
                int[] point = queue.poll();
                //先检查这个点是不是我们想要的点
                int x = point[0];int y = point[1];
                for(int i = 0;i<4;i++){
                    int tx = x + steps[i][0];
                    int ty = y + steps[i][1];
                    if(tx<0 || ty<0 || tx>=n || ty>=m){
                        continue;
                    }
                    if(grid[tx][ty] == 0){
                        grid[tx][ty] = 2;
                        queue.offer(new int[]{tx,ty});
                    }
                    if(grid[tx][ty] == 1){
                        return ans;
                    }
                }
            }
        }
        return ans;
    }
}
